package solutions.leetcode.easy;

import solutions.lib.BaseSolution;

import java.util.Arrays;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/heaters/">475.供暖器</a>
 */
public class Solution475 extends BaseSolution {

    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int p1 = 0, p2 = 0;
        int min = 0;
        while (p1 < houses.length) {
            while (p2 + 1 < heaters.length && heaters[p2 + 1] <= houses[p1]) {
                p2++;
            }
            int nextDis = p2 + 1 < heaters.length ? heaters[p2 + 1] - houses[p1] : Integer.MAX_VALUE;
            min = Math.max(Math.min(nextDis, Math.abs(houses[p1] - heaters[p2])), min);
            p1++;
        }
        return min;
    }

    public static void main(String[] args) {
        Solution475 solution = new Solution475();
        System.out.println(solution.findRadius(new int[]
                        {1, 2, 3, 4}
                , new int[]
                        {1, 4}
        ));
    }
}